#ifndef __BILINKED_LIST_H__
#define __BILINKED_LIST_H__

#include "common.h"

namespace algo
{


//Definition for bi-linked list.
template<class T>
class BiLinkedList
{
public:
    
struct BiNode {
    std::shared_ptr<T> val;
    std::shared_ptr<BiNode> prev;
    std::shared_ptr<BiNode> next;

    BiNode() :  val(NULL), prev(NULL), next(NULL) {    }

    BiNode(const BiNode& node) :  val(node.val), prev(node.prev), next(node.next) {    }

    BiNode& operator=(const BiNode &node)
    {
        val = node.val;
        prev = node.prev;
        next = node.next;
        return *this;
    }

    T& operator*() const
    {
        return *val;
    }

    BiNode& operator++()
    {
        if (next)
        {
            *this = *next;
        }
        else
        {
            val = NULL;
            prev = NULL;
            next = NULL;
        }
        return *this;
    }

    BiNode& operator--()
    {
        if (prev && prev->prev)
        {
            *this = *prev;
        }
        else
        {
            val = NULL;
            prev = NULL;
            next = NULL;
        }
        return *this;
    }

    bool operator==(const BiNode &other)
    {
        return val == other.val &&
                prev == other.prev &&
                next == other.next;
    }

    bool operator!=(const BiNode &other)
    {
        return !(*this == other);
    }

    bool valid()    const
    {
        return val != NULL ||
                prev != NULL ||
                next != NULL;
    }

};

typedef BiNode iterator;
typedef const BiNode const_iterator;


private:

    std::shared_ptr<BiNode> head;
    std::shared_ptr<BiNode> tail;
    int listSize;

public:
    BiLinkedList();

	virtual ~BiLinkedList();

    void append(T new_val);
    void add(T new_val);
    void add(int index, T new_val);

    std::shared_ptr<BiNode> insertBefore(iterator before, T new_val);
    std::shared_ptr<BiNode> insertAfter(iterator after, T new_val);

    virtual std::shared_ptr<T> get(int index);
    virtual std::shared_ptr<T> getFirst();
    virtual std::shared_ptr<T> getLast();

    virtual bool remove(int index);
    virtual bool removeFirst();
    virtual bool removeLast();

    bool empty();
    size_t size() const;

    void swap(int x, int y);

    void swap(std::shared_ptr<BiNode> pX, std::shared_ptr<BiNode> pY);
    
public:
    iterator begin()
    {
        return *(head->next);
    }

    iterator end()
    {
        return BiNode();
    }

    iterator rbegin()
    {
        return *tail;
    }

    iterator rend()
    {
        return BiNode();
    }

public:

    std::shared_ptr<BiNode> getNodeForward(int index)
    {
        std::shared_ptr<BiNode> hNode = head;
        int c = 0;

        while (c <= index && hNode->next)
        {
            hNode = hNode->next;
            if (c == index)
            {
                break;
            }
            ++c;
        }
        return hNode;
    }

    std::shared_ptr<BiNode> getNodeReverse(int index)
    {

        std::shared_ptr<BiNode> hNode = tail;
        int c = listSize - 1;

        while (c >= index && hNode)
        {
            if (c == index)
            {
                break;
            }
            hNode = hNode->prev;
            --c;
        }
        return hNode;
    }

    std::shared_ptr<BiNode> getNode(int index)
    {
        if (index < 0 || index >= listSize)
        {
            throw index_out_of_bounds();
        }

        if (index < listSize / 2)
        {
            return getNodeForward(index);
        }
        else
        {
            return getNodeReverse(index);
        }
    }

    std::shared_ptr<BiNode> getFirstNode()
    {
        if (empty())
        {
            throw empty_list();
        }
        return head->next;
    }

    std::shared_ptr<BiNode> getLastNode()
    {
        if (empty())
        {
            throw empty_list();
        }
        return tail;
    }

public:
    template<typename Fn>
    void sort(Fn const& comp);
private:
    template<typename Fn>
    void sort_c(int p, int r, Fn const& comp);

    template<typename Fn>
    int patition(int p, int r, Fn const& comp);
};


template<typename T>
BiLinkedList<T>::BiLinkedList() : head(new BiNode), tail(head), listSize(0)
{
}

template<typename T>
BiLinkedList<T>::~BiLinkedList()
{
}

template<typename T>
void BiLinkedList<T>::append(T new_val)
{
    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<BiNode> p(new BiNode);
    p->val = new_data;
    p->next = tail->next;
    p->prev = tail;
    tail->next = p;
    tail = p;

    ++listSize;
}

template<typename T>
void BiLinkedList<T>::add(T new_val)
{
    append(new_val);
}

template<typename T>
void BiLinkedList<T>::add(int index, T new_val)
{
    if (index < 0 || index > listSize)
	{
		throw index_out_of_bounds();
	}

    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<BiNode> p(new BiNode);
    p->val = new_data;

    std::shared_ptr<BiNode> prevNode;
    if (0 == index)
    {
        prevNode = head;
    }
    else
    {
        prevNode = getNode(index - 1);
    }
    p->next = prevNode->next;
    p->prev = prevNode;
    if (prevNode->next)
    {
        prevNode->next->prev = p;
    }
    else
    {
        tail = p;
    }
    prevNode->next = p;

    ++listSize;
}

template<typename T>
std::shared_ptr<typename BiLinkedList<T>::BiNode> BiLinkedList<T>::insertBefore(iterator before, T new_val)
{
    if (before == end())
    {
        throw index_out_of_bounds();
    }

    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<BiNode> pNew(new BiNode);

    std::shared_ptr<BiNode> pPrev = before.prev;
    std::shared_ptr<BiNode> pBefore = pPrev->next;

    pNew->val = new_data;
    pPrev->next = pNew;
    pNew->prev = pPrev;

    pBefore->prev = pNew;
    pNew->next = pBefore;

    ++listSize;

    return pNew;
}

template<typename T>
std::shared_ptr<typename BiLinkedList<T>::BiNode> BiLinkedList<T>::insertAfter(iterator after, T new_val)
{
    if (after == end())
    {
        throw index_out_of_bounds();
    }

    std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_val)));
    std::shared_ptr<BiNode> pNew(new BiNode);

    std::shared_ptr<BiNode> pNext = after.next;
    std::shared_ptr<BiNode> pAfter = (pNext) ? pNext->prev : tail;
    
    pNew->val = new_data;
    pNew->prev = pAfter;
    pNew->next = pNext;
    pAfter->next = pNew;

    if (pNext)
    {
        pNext->prev = pNew;
    }
    else
    {
        tail = pNew;
    }
    ++listSize;

    return pNew;
}

template<typename T>
std::shared_ptr<T> BiLinkedList<T>::get(int index)
{
    return getNode(index)->val;
}

template<typename T>
std::shared_ptr<T> BiLinkedList<T>::getFirst()
{
    return getFirstNode()->val;
}

template<typename T>
std::shared_ptr<T> BiLinkedList<T>::getLast()
{
    return getLastNode()->val;
}

template<typename T>
bool BiLinkedList<T>::empty()
{
    return 0 == listSize;
}

template<typename T>
size_t BiLinkedList<T>::size()  const
{
    return listSize;
}

template<typename T>
bool BiLinkedList<T>::remove(int index)
{
    if (index < 0 || index >= listSize)
    {
        throw index_out_of_bounds();
    }

    std::shared_ptr<BiNode> pNode = getNode(index);

    pNode->prev->next = pNode->next;
    if (pNode->next)
    {
        pNode->next->prev = pNode->prev;
    }
    else
    {
        tail = pNode->prev;
    }

    --listSize;

    return true;
}

template<typename T>
bool BiLinkedList<T>::removeFirst()
{
    return remove(0);
}

template<typename T>
bool BiLinkedList<T>::removeLast()
{
    return remove(listSize - 1);
}

template<typename T>
void BiLinkedList<T>::swap(int x, int y)
{
	if (x < 0 || y < 0 || x >= listSize || y >= listSize)
	{
		throw index_out_of_bounds();
	}

    if (x == y) 
    {
        return ;
    }

	// x must less than y
	if (x > y)
	{
		int tmp = x;
		x = y;
		y = tmp;
	}

	std::shared_ptr<BiNode> prevX = NULL;
	std::shared_ptr<BiNode> prevY = NULL;

	std::shared_ptr<BiNode> hNode = head;
	int c = 0;

	while (hNode && !prevY)
	{
		if (c == x)
		{
			prevX = hNode;
		}

		if (c == y)
		{
			prevY = hNode;
		}

		++c;
		hNode = hNode->next;
	}

	std::shared_ptr<BiNode> pX = prevX->next;
	std::shared_ptr<BiNode> pY = prevY->next;

	hNode = y - 1 == x ? pX : pX->next;

    prevX->next = pY;
    if (pY->next)
    {
        pY->next->prev = pX;
    }
    else
    {
        tail = pX;
    }
    pY->prev = prevX;
    pX->next = pY->next;

    pY->next = hNode;
    hNode->prev = pY;
	
	if (y - 1 != x)
	{
		prevY->next = pX;
        pX->prev = prevY;
	}
}

template<typename T>
void BiLinkedList<T>::swap(std::shared_ptr<BiNode> pX, std::shared_ptr<BiNode> pY)
{
    if (!pX || !pY)
    {
        throw index_out_of_bounds();
    }

    if (pX == pY)
    {
        return ;
    }
    
    bool adjacent = false;
    if (pX->next == pY)
    {
        adjacent = true;
    }
    else if (pY->next == pX)
    {
        // x must in front of y
        std::shared_ptr<BiNode> tmp = pX;
        pX = pY;
        pY = tmp;
        adjacent = true;
    }

    std::shared_ptr<BiNode> prevX = pX->prev;
    std::shared_ptr<BiNode> prevY = pY->prev;
    std::shared_ptr<BiNode> nextX = pX->next;
    std::shared_ptr<BiNode> nextY = pY->next;

    prevX->next = pY;
    pY->prev = prevX;

    if (adjacent)
    {
        pY->next = pX;
        pX->prev = pY;
    }
    else
    {
        prevY->next = pX;
        pX->prev = prevY;
        
        pY->next = nextX;
        nextX->prev = pY;
    }

    pX->next = nextY;
    if (nextY)
    {
        nextY->prev = pX;
    }
    else
    {
        tail = pX;
    }
}

template<typename T>
template<typename Fn>
void BiLinkedList<T>::sort(Fn const& comp)
{
    sort_c(0, listSize-1, comp);
}

template<typename T>
template<typename Fn>
void BiLinkedList<T>::sort_c(int p, int r, Fn const& comp)
{
    if (p >= r)
        return ;

    int q = patition(p, r, comp);

    sort_c(p, q - 1, comp);
    sort_c(q + 1, r, comp);

}

template<typename T>
template<typename Fn>
int BiLinkedList<T>::patition(int p, int r, Fn const& comp)
{
    std::shared_ptr<BiNode> pivot = getNode(r);
    int i, j;
    i = p;
    std::shared_ptr<BiNode> iNode = getNode(i);
    std::shared_ptr<BiNode> jNode(iNode);
    for (j = p; j < r; ++j)
    {
        if (comp(*(jNode->val), *(pivot->val)))
        {
            swap(iNode, jNode);
            iNode = iNode->next;
            ++i;
        }
        jNode = jNode->next;
    }
    swap(iNode, pivot);
    return i;
}



}   // namespace end




#endif

